﻿#ifndef LIST_H_
#define LIST_H_

#include<iostream>
#include<vector>

//单双链表及其反转-堆栈诠释
	
	//单链表结点
	struct ListNode {
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}
	};

		//反转链表
		// https://leetcode.cn/problems/reverse-linked-list/
		// 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
		//	单链表反转 迭代
		//	通过按照从前到后的顺序，先将前面的反转，但总体还是一个链表
		ListNode* reverseList0(ListNode* head);

		//	单链表反转 迭代
		// 参考左神的
		//	分为两个链表，一个是反转链表，一个是原链表，遍历时将原链表的头移动到反转链表的头
		ListNode* reverseList1(ListNode* head);


		//	单链表反转 递归
		ListNode* reverseList2(ListNode* head);

		//范围反转
		//https://leetcode.cn/problems/reverse-linked-list-ii/description/
		ListNode* reverseBetween(ListNode* head, int left, int right);


	// 双链表节点
	struct DoubleListNode {
	int val;
	DoubleListNode* pre;
	DoubleListNode* next;

	DoubleListNode() : val(0), pre(nullptr), next(nullptr) {}
	DoubleListNode(int x) : val(x), pre(nullptr), next(nullptr) {}
	DoubleListNode(int x, DoubleListNode* pre,DoubleListNode* next) : val(x), pre(pre), next(next) {}
	};


		//	双链表反转	迭代
		DoubleListNode* reverseList(DoubleListNode* head);


//合并两个有序链表
//https://leetcode.cn/problems/merge-two-sorted-lists/description/
//将两个升序链表合并为一个新的 升序 链表并返回
//新链表是通过拼接给定的两个链表的所有节点组成的
	ListNode* mergeTwoLists(ListNode* list1, ListNode* list2);


//两个链表相加
// 给你两个 非空 的链表，表示两个非负的整数
// 它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字
// 请你将两个数相加，并以相同形式返回一个表示和的链表。
// 你可以假设除了数字 0 之外，这两个数都不会以 0 开头
// 测试链接：https://leetcode.cn/problems/add-two-numbers/
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2);
	ListNode* addTwoNumbers2(ListNode* l1, ListNode* l2);


// 划分链表
// 给你一个链表的头节点 head 和一个特定值 x
// 请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
// 你应当 保留 两个分区中每个节点的初始相对位置
// 测试链接 : https://leetcode.cn/problems/partition-list/
	ListNode* partition(ListNode* head, int x);


/*
前置知识：
讲解009~012-链表入门内容、讲解021-归并排序
讲解026-哈希表的使用、讲解029-排序算法的稳定性

链表类题目注意点：
1，如果笔试中空间要求不严格，直接使用容器来解决链表问题
2，如果笔试中空间要求严格、或者在面试中面试官强调空间的优化，需要使用额外空间复杂度O(1)的方法
3，最常用的技巧-快慢指针
4，链表类题目往往都是很简单的算法问题，核心考察点也并不是算法设计，是coding能力
5，这一类问题除了多写多练没有别的应对方法

个人建议：链表类问题既然练的就是coding，那么不要采取空间上讨巧的方式来练习

注意：链表相关的比较难的问题是约瑟夫环问题，会在【扩展】阶段讲解，变形很多会单独出一期视频讲解

*/

//题目1: 返回两个无环链表相交的第一个节点
// 返回两个无环链表相交的第一个节点
// 测试链接 : https://leetcode.cn/problems/intersection-of-two-linked-lists/
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB);

//题目2: 每k个节点一组翻转链表
// 每k个节点一组翻转链表
// 测试链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/
ListNode* reverseKGroup(ListNode* head, int k);

//题目3: 复制带随机指针的链表
// 复制带随机指针的链表
class Node {
public:
	int val;
	Node* next;
	Node* random;

	Node(int _val) {
		val = _val;
		next = NULL;
		random = NULL;
	}
};
// 测试链接 : https://leetcode.cn/problems/copy-list-with-random-pointer/
Node* copyRandomList(Node* head);

//题目4: 判断链表是否是回文结构。这个题的流程设计甚至是考研常用。快慢指针找中点。

// 判断链表是否是回文结构
// 测试链接 : https://leetcode.cn/problems/palindrome-linked-list/
bool isPalindrome(ListNode* head);

//题目5: 返回链表的第一个入环节点。快慢指针找中点。
// 返回链表的第一个入环节点
// 测试链接 : https://leetcode.cn/problems/linked-list-cycle-ii/
ListNode* detectCycle(ListNode* head);

//题目6: 在链表上排序。要求时间复杂度O(n* log n)，额外空间复杂度O(1)，还要求排序有稳定性。
// 排序链表
// 要求时间复杂度O(n*logn)，额外空间复杂度O(1)，还要求稳定性
// 数组排序做不到，链表排序可以
// 测试链接 : https://leetcode.cn/problems/sort-list/
ListNode* sortList(ListNode* head);

/*
注意：
这些题目往往难度标为“简单”，是因为用容器解决真的很简单
但是不用容器、实现额外空间复杂度O(1)的方法并不轻松，包括很多提交的答案也都没有符合要求

*/
#endif //LIST_H_
